//https://leetcode.cn/problems/design-graph-with-shortest-path-calculator/description/?envType=daily-question&envId=2024-03-26https://leetcode.cn/problems/design-graph-with-shortest-path-calculator/description/?envType=daily-question&envId=2024-03-26


class Graph {
    const int INF = INT_MAX / 3;
    vector<vector<int>> g;

public:
    Graph(int n, vector<vector<int>>& edges) : g(n, vector<int>(n, INF)){
        for (int i = 0; i < n; ++i) g[i][i] = 0;
        for (auto& e : edges) {
            g[e[0]][e[1]] = e[2];
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                if (g[i][k] == INF) continue;
                for (int j = 0; j < n; j++) {
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
                }
            }
        }
    }
    
    void addEdge(vector<int> edge) {
        int x = edge[0], y = edge[1], w = edge[2];
        int n = g.size();
        if (w >= g[x][y]) return;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                g[i][j] = min(g[i][j], g[i][x] + w + g[y][j]);
            }
        }
    }
    
    int shortestPath(int node1, int node2) {
        return g[node1][node2] < INF ? g[node1][node2] : -1;
    }
};